package com.cjm.algorithm.backtracking;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Ti131 {
    public static void main(String[] args) {
        System.err.println("abc".substring(0,3));
        Ti131 ti131 = new Ti131();
        List<List<String>> aab = ti131.partition("aab");
        System.err.println("OK");
    }

    private boolean isHuiWenString(String aaa) {
        if (aaa.isEmpty()) {
            return false;
        }
        if (aaa.length() == 1) {
            return true;
        }
        int start = 0;
        int end = aaa.length() - 1;

        // 这不就是相当于两指针吗？对撞指针
        for (int i = start, j = end; i<=j; i++, j--) {
            if (aaa.charAt(i) != aaa.charAt(j)) return false;
        }
        return true;
    }

    List<List<String>> res = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();

    public List<List<String>> partition(String s) {
        method(s, 0);
        return res;
    }

    private void method(String s, int startIndex) {
        // 从startIndex开始切， 切的时候包括了startIndex的字符
        // 这里的意思，就是已经到最后一个字符了呗
        if (startIndex == s.length()) {
            ArrayList<String> e = new ArrayList<>(path);
            Collections.reverse(e);
            res.add(e);
        }
        for (int i = startIndex+1; i <= s.length(); i++) {
            // 这里就是一个问题， 在那里切割？[startIndex, i)
            String substring = s.substring(startIndex, i);
            if (!isHuiWenString(substring)) {
                // 如果不是回文串的话， 那么继续
                // 那么意思， [startIndex, i)不是回文串， 继续往下走
                // [startIdex, i+1)， 直到截取到最后一个
                continue;
            }
            // 放入
            path.addFirst(substring);
            // 这里还是i哦, 这里因为是截取到i了， 所以下一个数是i， 不是startIndex
            // 所以上面的那几个字不合适， 什么叫“这里还是i哦”
            method(s, i);
            // 弹出
            path.pollFirst();
        }
    }
}
